/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/multiply-strings
   @Language: C++
   @Datetime: 19-06-06 14:39
   */

// Method 1, Time O(m*n), Space O(m+n), Time 12ms
class Solution {
public:
	string multiply(string &num1, string &num2) {
		int l1=num1.length(), l2=num2.length();
		string res;
		for(int i=l1; i--;){
			for(int j=l2, k=l1-i-1, carry=0; j-->0 || carry; ++k){
				if(j>-1) carry+=(num1[i]-'0')*(num2[j]-'0');
				if(k<res.length()){
					carry+=res[k]-'0';
					res[k]=carry%10+'0';
				}
				else res.push_back(carry%10+'0');
				carry/=10;
			}
		}
		for(; res.back()=='0'; res.pop_back());
		reverse(res.begin(),res.end());
		return res.length()?res:"0";
	}
};

// Method 2, Time O(m*n), Space O(m+n), Time 8ms
class Solution {
public:
	string multiply(string &num1, string &num2) {
		int n=num1.length(), m=num2.length();
		if ((n==1 && num1[0]=='0') || (m==1 && num2[0]=='0')) return "0";
		string res(n+m,'0');
		for(int i=n, l=n+m-1, carry=0; i-- || carry; --l){
			for(int j=m, k=l; j || carry; carry/=10){
				if (j) carry += (num1[i]-'0')*(num2[--j]-'0') + res[k]-'0';
				res[k--]=carry%10+'0';
			}
		}
		if (res[0]=='0') res.erase(0,1);
		return res;
	}
};
